* Jocul NIM clasic *

Se considera N gramezi de pietre. Fiecare juactor poate lua cate pietre vrea din
orice gramada. Castigatorul este cel care ia ultima piatra. 

- daca avem o gramada jucatorul care urmeaza sa mute va castiga
- daca avem 2 gramezi jucatorul are stategie de castig atunci cand nr de 
pietre din prima gramada este diferit de numarul de pietre din cea de-a doua
: el va lua cate pietre sunt necesare pt ca nr de pietre sa fie adus la numarul 
celei de-a doua gramezi
- daca nr de gramezi este mai mare ca 2 : vom reperezenta numerele in baza 2 ,
 iar o stare castigatoare este una in care suma XOR a nr. din gramezi difera de 0

Demonstratie:  dintr-o stare cu suma xor 0 , prin orice mutare ajungem evident la
o suma xor diferita de 0 ; fie x - suma xor , y - o gramada care are bitul cel mai
semnificativ din totate gramezile cu nr de cifre binare mai mici decat cel al sumei
 ( ex pt 1,3,5,7 => y va fi 5(101) sau 7(111) ) o mutare castigatoare repezinta
 extragerea din gramada gasita care are y pietre a ( y - ( x ^ y ) ) pietre.

* Jocul NIM cu adaugare de pietre *
- avand posibilitatea de a aduga un numar finit de pietre , doar jucatorul in 
dezavataj se va folosi de ele , insa celalt jucator va lua acele pietre 
- castigatorul va fi jucatorul 1 daca suma xor a starilor initiale este cea dorita
( > 0 )

* Inversul jocului NIM *
Acealsi enunt , doar ca jucatourl care ia ultima piatra pierde. Jucatorul muta la 
fel ca in jocul NIM , cu exceptia cazului in care mutarea lasa doar gramezi cu o
piatra si nr gramezilor cu o piatra va fi par. Atunci luam intreaga gramada.

*** Numere Sprague-Grundy ***

Se considera un graf aciclic care contine in noduri cativa pioni, jucatorii 
alterneaza la mutare si fiecare poate muta cate un pion pe un arc care iese din
nodul in care este situat pionul. Pierde jucatorul care nu mai poate muta.

* Jocul cu un pion *

O sa analizam jocul cu un singur pion. Considerand ca cei 2 jucatori joaca optim
putem numi o pozitie P-avantajoasa daca anterior este in avantaj in avantaj si N-
avantajoasa daca urmatorul jucator este in avantaj. Avand in vedere ca avem un
singur pion , o pozitie avantajoasa este invintoare. Vom marca in graf ( orientat 
aciclic ) nodurile de margine ca fiind noduri P. Mai departe un nod este P daca 
toti urmasii sai sunt P. Un nod este N daca are cel putin un urmas P.

O N-pozitie este avantajoasa pentru jucatorul 1.
O P-pozitie este avantajoasa pentru jucatorul 2.

Nu putem afla daca , avand G1 , G2 , 2 jocuri impartiale , nu putem sti daca un nod
va fi N sau P. Astfel trebuie sa generalizam functia N / P.

* Functia S-G *

Definim o stare SG ca fiind un numar natural { 0 , 1 , 2 , ... }.
Definim functia Mex pentru multimi ca fiind Mex S = min( N - S ).

Mex( extrema ) = 1;

Notam functia S-G cu g.
Proprietati generale: 
- un nod e P <=> g(v)=0
- pentru un joc G=G1+G2 cu v=v1*v2, atunci g( v ) este g( v1 ) ^ g( v2 ).

Generam in O(N+M) graful S-G. Rezultatul jocului este suma XOR a tuturor starilor 
din graful S-G.

